#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

class Trie{
    private:
    vector<Trie*> children;
    bool isEnd;

    Trie* searchPrefix(string prefix){
        Trie* node = this;
        for(char ch : prefix){
            ch = ch - 'a';
            if(node->children[ch] == nullptr){
                return nullptr;
            }
            node = node->children[ch];
        }
        return node;
    }

    public:
    Trie():children(26, nullptr), isEnd(false){};

    void insert(string word){
        Trie* node = this;
        for(char ch: word){
            ch = ch - 'a';
            if(node->children[ch] == nullptr){
                node->children[ch] = new Trie();
            }
            node = node->children[ch];
        }
        node->isEnd = true;
    }

    bool search(string word){
        Trie* node = searchPrefix(word);
        if(node != nullptr && node->isEnd == true){
            return true;
        }else{
            return false;
        }
    }

    bool startsWith(string word){
        Trie* node = searchPrefix(word);
        if(node != nullptr){
            return true;
        }else{
            return false;
        }
    }
};

void test(){
    Trie *s = new Trie();
    s->insert("apple");
    cout << s->search("apple") << endl;
    cout << s->search("app") << endl;
    cout << s->startsWith("app") << endl;
    s->insert("app");
    cout << s->search("app") << endl;
}

int main(void){
    test();

    return 0;
}